#include <bits/stdc++.h>

using namespace std;

// IPO
// 给你n个项目，对于每个项目i
// 它都有一个纯利润profits[i]
// 和启动该项目需要的最小资本capital[i]
// 最初你的资本为w，当你完成一个项目时，你将获得纯利润，添加到你的总资本中
// 总而言之，从给定项目中选择最多k个不同项目的列表
// 以最大化最终资本，并输出最终可获得的最多资本
// 测试链接 : https://leetcode.cn/problems/ipo/

class Solution 
{
public:
    struct Project
    {
        int p; // 纯利润
        int c; // 需要的启动金
    };

    // 大根堆使用，比较的是纯利润
    struct Less
    {
        bool operator()(const Project& x, const Project& y)
        {
            return x.p < y.p;
        }
    };

    // 小根堆使用，比较的是需要的启动金
    struct Greater
    {
        bool operator()(const Project& x, const Project& y)
        {
            return x.c > y.c;
        }
    };

    int findMaximizedCapital(int k, int w, vector<int>& profit, vector<int>& cost) 
    {
        int n = profit.size();
        // 需要的启动金小根堆
		// 代表被锁住的项目
        priority_queue<Project, vector<Project>, Greater> heap1;
		// 利润大根堆
		// 代表被解锁的项目
        priority_queue<Project, vector<Project>, Less> heap2;
        for(int i = 0; i < n; ++i) heap1.push({profit[i], cost[i]});
        while(k > 0)
        {
            while(!heap1.empty() && heap1.top().c <= w)
            {
                heap2.push(heap1.top());
                heap1.pop();
            }
            // 已经没有解锁的项目了
            if(heap2.empty()) break;
            w += heap2.top().p;
            heap2.pop();
            --k;
        }
        return w;
    }
};


class Solution 
{
public:
    int findMaximizedCapital(int k, int w, vector<int>& profit, vector<int>& cost) 
    {
        int n = profit.size();
        array<int, 2> arr[n];
        for(int i = 0; i < n; ++i) arr[i] = {cost[i], profit[i]};
        sort(arr, arr + n, [](auto& a, auto& b){
            return a[0] < b[0];
        });
        priority_queue<int> heap; // 大根堆，存储的是纯利润
        for(int i = 0, cur = 0; i < k; ++i)
        {
            while(cur < n && arr[cur][0] <= w)
            {
                heap.push(arr[cur][1]);
                ++cur;
            }
            // 已经没有解锁的项目了
            if(heap.empty()) break;
            w += heap.top();
            heap.pop();
        }
        return w;
    }
};